"""
https://leetcode.cn/problems/sliding-window-maximum/description/

239. 滑动窗口最大值
困难
相关标签
premium lock icon
相关企业
提示
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

 

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7
示例 2：

输入：nums = [1], k = 1
输出：[1]
 

提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length

"""

import collections
from typing import List


class Solution:
    """
    滑动窗口大小固定
    暴力求解的时间复杂度是O(n*k)

    优先队列可以比较舒服的解决此题。

    将前k个元素，维护一个大小固定但元素规律性变化，能时刻提供最大值的数据结构。

    解题思路的核心，是最小值队列。舍弃不必的大量元素。
    是一个巧妙的解题思路。
    

    """
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        # 双向队列，记录最大元素索引双向队列，简称队列
        q = collections.deque()
        # 初始化数据结构。获得一个内小外大的索引栈。
        for i in range(k):
            # 如果队列存在元素索引，且当前元素比队列最近元素索引对应的值大，则弹出队列的元素索引，直到队列的最近元素索引对应的值小于当前元素
            while q and nums[i] >= nums[q[-1]]:
                q.pop()
            # 时刻添加元素索引
            q.append(i)

        # 此时队列首元素索引对应的值，即为当前窗口的最小值
        ans = [nums[q[0]]]
        # 遍历后面的元素
        for i in range(k, n):
            # 先考虑新元素对队列的影响，维护索引栈
            while q and nums[i] >= nums[q[-1]]:
                q.pop()
            q.append(i)
            # 判断最小值索引，是否已经不在窗口中。如果idx<=i-k，则idx不在窗口中
            # 这里使用while的原因是：每次仅对最小值索引进行判断。
            # 因此可能存在某次判断，最小值索引仍在队列中，但次小值索引不在队列中了。
            # 此时引用最小值索引，不影响窗口最小值维护结果，但影响后续窗口的最小值。因此每次需要用while而不是if来保证当前最小值索引在当前窗口内
            while q[0] <= i - k:
                # 此时弹出最小值索引
                q.popleft()
            # 将最小值放到结果队列中
            ans.append(nums[q[0]])
        
        return ans
        pass

if __name__=='__main__':
    pass